package _dp

import org.junit.Assert
import org.junit.Test

/**
 *
 * https://leetcode.cn/problems/count-numbers-with-unique-digits/description/?envType=problem-list-v2&envId=backtracking
 * ```
 * 357. 统计各位数字都不同的数字个数
 *
 * 给你一个整数 n ，统计并返回各位数字都不同的数字 x 的个数，其中 0 <= x < 10n 。
 *
 * 示例 1：
 * 输入：n = 2
 * 输出：91
 * 解释：答案应为除去 11、22、33、44、55、66、77、88、99 外，在 0 ≤ x < 100 范围内的所有数字。
 *
 * 示例 2：
 * 输入：n = 0
 * 输出：1
 * ```
 *
 */
class leetcode_357 {
    @Test
    fun test_1() {
        val result = countNumbersWithUniqueDigits(2)
        val expected = 91
        Assert.assertEquals(expected, result)
    }

    @Test
    fun test_2() {
        val result = countNumbersWithUniqueDigits(0)
        val expected = 1
        Assert.assertEquals(expected, result)
    }


    private fun countNumbersWithUniqueDigits(n: Int): Int {
        /**
        https://blog.csdn.net/qq_40682833/article/details/124091652
        动态规划
        1 确定dp数组（dp table）以及下标的含义 : 当位数 为n 时，可能的个数
        2 确定递推公式
        n = 0, dp[0] = 1, f(0) = 1
        n = 1, dp[1] = 9, f(1) = dp[1] + f(0)  =  9 + 1 = 10
        n = 2, dp[2] = (10-1) * dp[1] = 81, f(2) = dp[2] + f(1) = 81
        n = n, dp[n] = (10 - (n-1) * dp[n-1], f(n) = dp[n] + f(n-1)
        3 dp数组如何初始化
        4 确定遍历顺序
        5 举例推导dp数组：打印数组
         */

        // 1 dp[n]
        // 2 公式
        // n = n, dp[n] = (10 - (n-1) * dp[n-1], f(n) = dp[n] + f(n-1)
        // 3 dp 初始化
        // 4 遍历
        // 5 打印

        if (n == 0) {
            return 1
        }

        if (n == 1) {
            return 10
        }

        // 1 dp[n]
        val dp: IntArray = IntArray(n + 1)
        dp[0] = 1 // 1
        dp[1] = 9 // 10

        var result = 10
        for (i in 2..n) {
            dp[i] = (10 - (i - 1)) * dp[i - 1]
            result = dp[i] + result
        }
        return result
    }
}